#include <stdio.h>

// 函数声明
int gcd(int a, int b);
int lcm(int a, int b);

int main()
{
  int num1, num2;

  // 输入两个整数
  printf("请输入两个整数: ");
  scanf("%d %d", &num1, &num2);

  // 计算并输出结果
  printf("%d 和 %d 的最大公约数是: %d\n", num1, num2, gcd(num1, num2));
  printf("%d 和 %d 的最小公倍数是: %d\n", num1, num2, lcm(num1, num2));

  return 0;
}
// 欧几里得算法求最大公约数
int gcd(int a, int b)
{
  // 辗转相除法核心逻辑
  while (b != 0)
  {
    int temp = b;
    b = a % b; // 取余数
    a = temp;  // 更新a为原来的b
  }
  return a; // 当b为0时，a就是最大公约数
}

// 利用公式：最小公倍数 = 两数乘积 / 最大公约数
int lcm(int a, int b)
{
  // 先判断是否有0，避免除以0错误
  if (a == 0 || b == 0)
  {
    return 0;
  }
  // 计算乘积时先除以gcd，避免可能的整数溢出
  return (a / gcd(a, b)) * b;
}
